struct Node
{
    int v;
    int w;
    Node(int a, int b) :v(a), w(b){}
};

struct DEdge
{
    int V1;
    int V2;
    int Weight;
    DEdge() {};
    DEdge(int a, int b, int c) { V1 = a; V2 = b; Weight = c;}
    friend bool operator < (const DEdge& E1, const DEdge& E2)
    {
        return E1.Weight < E2.Weight;
    }
    friend bool operator > (const DEdge& E1, const DEdge& E2)  // 重载>操作符用于实现顶端元素最小的优先队列
    {
        return E1.Weight > E2.Weight;
    }
};

void MakeSet(vector<int>& uset, int n)   //创建并查集
{
    uset.resize(n);
    for (int i = 0; i < n; i++)
        uset[i] = i;
}

int FindSet(vector<int>& uset, int u)   //查找当前元素所在集合的代表元
{
    int i = u;
    while (uset[i] != i) i = uset[i];
    return i;
}

void Kruskal(vector<DEdge> edges, int n)    // Kruskal算法
{
    vector<int> uset;
    vector<DEdge> MST;
    int Cost = 0, e1, e2;
    MakeSet(uset, n);
    for (int i = 0; i < edges.size(); i++) //按权值从小到大的顺序取边
    {
        e1 = FindSet(uset, edges[i].V1);
        e2 = FindSet(uset, edges[i].V2);
        if (e1 != e2) //若当前边连接的两个结点在不同集合中，选取该边并合并这两个集合
        {
            MST.push_back(edges[i]);
            Cost += edges[i].Weight;
            uset[e1] = e2; //合并当前边连接的两个顶点所在集合
        }
    }
    cout << "Results of the Kruskal algorithm: " << endl;
    cout << "Cost = " << Cost << endl;
    cout << "Edges:" << endl;
    for (int j = 0; j < MST.size(); j++)
        cout << "<" << MST[j].V1 << ", " << MST[j].V2 << ">, Weight = " << MST[j].Weight << endl;
    cout << endl;
}

void Prim(vector<list<Node>> &Adj, int n, int m)    // Prim算法
{
    priority_queue<DEdge, vector<DEdge>, greater<>> Q;  // 重载>操作符，实现顶端元素最小的优先队列

    int Cost = 0;                  // 用于统计最小生成树的权值之和
    vector<DEdge> MST;             // 用于保存最小生成树的边
    vector<int> uset(n,0);  // 用数组来实现并查集
    DEdge E(0, 0, 0);
    for (int i = 0; i < n; i++)    //并查集初始化
        uset[i] = i;

    // 根据Prim算法，开始时选取结点0，并将结点0与剩余部分的边保存在优先队列中
    // 循环中每次选取优先队列中权值最小的边，并更新优先队列
    for (auto it = Adj[0].begin(); it != Adj[0].end(); it++)
        Q.push(DEdge(0, it->v, it->w));


    while (!Q.empty())
    {
        E = Q.top();
        Q.pop();
        if (FindSet(uset, E.V2) != 0)
        {
            Cost += E.Weight;
            MST.push_back(E);
            uset[E.V2] = E.V1;
            for (auto it = Adj[E.V2].begin(); it != Adj[E.V2].end(); it++)
                if (FindSet(uset, it->v) != 0)
                    Q.push(DEdge(E.V2, it->v, it->w));
        }
    }
    cout << "Results of the Prim algorithm:" << endl;
    cout << "Cost = " << Cost << endl;
    cout << "Edges:" << endl;
    for (int j = 0; j < MST.size(); j++)
        cout << "<" << MST[j].V1 << ", " << MST[j].V2 << ">, Weight = " << MST[j].Weight << endl;
    cout << endl;
}

void BuildDGraph_PrimAndKruskal()    // 建立按边储存的图并调用最小生成树算法
{
    int u, v, w, n, m;
    cin >> n >> m;

    vector<list<Node>> Adj;             // prim用
    Adj.assign(n, list<Node>());

    vector<DEdge> Ve;                   // kruskal用
    Ve.resize(m);

    for (int i = 0; i < m; i++)
    {
        cin >> u >> v >> w;
        Adj[u].push_back(Node(v,w));
        Adj[v].push_back(Node(u,w));

        Ve[i].V1 = u;
        Ve[i].V2 = v;
        Ve[i].Weight = w;
    }

    sort(Ve.begin(), Ve.end());   //排序之后，可以以边权值从小到大的顺序选取边
    Kruskal(Ve, n);

    Prim(Adj, n, m);

    return;
}